/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM66 最长公共子串
 * <a href="https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac?tpId=295&tqId=991150&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2022-11-05
 * Time: 14:30
 */

//给定两个字符串str1和str2,输出两个字符串的最长公共子串
//题目保证str1和str2的最长公共子串存在且唯一

public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    //动态规划解决
    /*public String LCS (String str1, String str2) {
        //由于题目保证最长公共子串存在且唯一，因此不需要进行判空处理
        int len1 = str1.length();
        int len2 = str2.length();
        //定义dp[i][j]表示字符串str1中第i个字符和str2种第j个字符为最后一个元素所构成的最长公共子串
        int[][] dp = new int[len1 + 1][len2 + 1];
        int maxLen = 0;  //记录最长字串的长度
        int maxLastIndex = 0; //记录最长字串末尾字符在s1中的位置
        for (int i = 1; i < len1 + 1; i++) {
            for (int j = 1; j < len2 + 1; j++) {
                //根据递归推理
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) { //字符相等时
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    //判断是否为最长字串
                    if (dp[i][j] > maxLen) {
                        maxLen = dp[i][j];
                        maxLastIndex = i - 1;
                    }
                } else {   //字符不相等时
                    dp[i][j] = 0;
                }
            }
        }
        return str1.substring(maxLastIndex - maxLen,maxLastIndex + 1);
    }*/

    //动态规划改进
    //上面我们使用的是二维数组，我们发现计算当前位置的时候之和左上角的值有关，所以我们可以把二维数组变为一维数组，
    //注意第2个for循环要进行倒叙，因为后面的值要依赖前面的值，如果不倒叙，前面的值会被覆盖，导致结果错误
    public String LCS(String str1, String str2) {
        int maxLenth = 0;//记录最长公共子串的长度
        //记录最长公共子串最后一个元素在字符串str1中的位置
        int maxLastIndex = 0;
        int[] dp = new int[str2.length() + 1];
        for (int i = 0; i < str1.length(); i++) {
            //注意这里是倒叙
            for (int j = str2.length() - 1; j >= 0; j--) {
                //递推公式，两个字符相等的情况
                if (str1.charAt(i) == str2.charAt(j)) {
                    dp[j + 1] = dp[j] + 1;
                    //如果遇到了更长的子串，要更新，记录最长子串的长度，
                    //以及最长子串最后一个元素的位置
                    if (dp[j + 1] > maxLenth) {
                        maxLenth = dp[j + 1];
                        maxLastIndex = i;
                    }
                } else {
                    //递推公式，两个字符不相等的情况
                    dp[j + 1] = 0;
                }
            }
        }
        //最字符串进行截取，substring(a,b)中a和b分别表示截取的开始和结束位置
        return str1.substring(maxLastIndex - maxLenth + 1, maxLastIndex + 1);
    }
}
